Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST‘s (binary search trees) that store values 1…n.

For example,

Given n = 3, your program should return all 5 unique BST’s shown below.

  1.    1         3     3      2      1
  2.     \       /     /      / \      \
  3.      3     2     1      1   3      2
  4.     /     /       \                 \
  5.    2     1         2                 3

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public List<TreeNode> generateTrees(int n) {
  12.       return helper(1, n);
  13.   }
  15.   List<TreeNode> helper(int lo, int hi) {
  16.     List<TreeNode> res = new ArrayList<>();
  18.     if (lo > hi) {
  19.       res.add(null);
  20.       return res;
  21.     }
  23.     if (lo == hi) {
  24.       res.add(new TreeNode(lo));
  25.       return res;
  26.     }
  28.     for (int i = lo; i <= hi; i++) {
  29.       List<TreeNode> left = helper(lo, i - 1);
  30.       List<TreeNode> right = helper(i + 1, hi);
  32.       for (TreeNode l : left) {
  33.         for (TreeNode r : right) {
  34.           TreeNode root = new TreeNode(i);
  35.           root.left = l;
  36.           root.right = r;
  37.           res.add(root);
  38.         }
  39.       }
  40.     }
  42.     return res;
  43.   }
  44. }